Méthode de type off-policy avec approximations

8. Méthodes par Gradient-TD

8.1. Introduction des concepts mathématiques

Utilité du projeté de l'erreur de Bellman

On va maintenant s'intéresser aux méthodes SGD permettant de minimiser l'erreur $\overline {PBE}$. Étant de vraies méthodes SGD, ces méthodes convergent de manière robuste, même dans le cas d'un apprentissage hors ligne et avec l'utilisation d'approximations non-linéaires.

L'idée de cette méthode est de développer un objectif lié à l'erreur TD. La méthode du gradient résiduel se basait sur l'erreur de Bellman pour faire cela, mais nous avons vu qu'elle souffre de plusieurs inconvénients, comme le fait qu'elle nécessite un double échantillonnage. Cette fois-ci, l'objectif va être construit en se basant sur le projeté de l'erreur de Bellman.

Notations matricielles

Rappelons pour commencer la vision géométrique de notre problématique, dans un exemple de situation où l'environnement possède par exemple trois états $S = \left( {{s_1},{s_2},{s_3}} \right)$ et le vecteur poids possède deux composantes $\textbf{w} \in \textbf{W} = {\left( {{w_1},{w_2}} \right)^T}$.

Dans cette situation, la fonction de la valeur d'un état $s$ de l'environnement s'exprime de la manière suivante :

$$v_{\textbf{w}}\left( s \right) = {\textbf{w}^T}\textbf{x}\left( s \right) = \sum\limits_{i = 1}^2 {{w_i}{x_i}\left( s \right)}$$

avec $\textbf{x}\left( s \right)$ le vecteur caractéristique :

$$\textbf{x}\left( s \right) = \left( {\begin{array}{*{20}{c}} {{x_1}\left( s \right)}\\ {{x_2}\left( s \right)} \end{array}} \right)$$

On a donc, pour l'ensemble des états de l'environnement, les trois fonctions des valeurs suivantes:

$$ \Rightarrow \left\{ {\begin{array}{*{20}{c}} {{v_\textbf{w}}({s_1}) = {\textbf{w}^T}\textbf{x}\left( {{s_1}} \right) = {w_1} \cdot {x_1}\left( {{s_1}} \right) + {w_2} \cdot {x_2}\left( {{s_1}} \right)}\\ {{v_\textbf{w}}({s_2}) = {\textbf{w}^T}\textbf{x}\left( {{s_2}} \right) = {w_1} \cdot {x_1}\left( {{s_2}} \right) + {w_2} \cdot {x_2}\left( {{s_2}} \right)}\\ {{v_\textbf{w}}({s_1}) = {\textbf{w}^T}\textbf{x}\left( {{s_3}} \right) = {w_1} \cdot {x_1}\left( {{s_3}} \right) + {w_2} \cdot {x_2}\left( {{s_3}} \right)} \end{array}} \right.$$

Les fonctions des valeurs des états de l'ensemble de l'environnement est donc le vecteur :

$${V_\textbf{w}} = \left( {\begin{array}{*{20}{c}} {{v_\textbf{w}}\left( {{s_1}} \right)}\\ {{v_\textbf{w}}\left( {{s_2}} \right)}\\ {{v_\textbf{w}}\left( {{s_3}} \right)} \end{array}} \right) = \left( {\begin{array}{*{20}{c}} {{w_1} \cdot {x_1}\left( {{s_1}} \right) + {w_2} \cdot {x_2}\left( {{s_1}} \right)}\\ {{w_1} \cdot {x_1}\left( {{s_2}} \right) + {w_2} \cdot {x_2}\left( {{s_2}} \right)}\\ {{w_1} \cdot {x_1}\left( {{s_3}} \right) + {w_2} \cdot {x_2}\left( {{s_3}} \right)} \end{array}} \right)$$

En définissant la matrice des vecteurs caractéristiques $X$ :

$$X = \left( {\begin{array}{*{20}{c}} {{\textbf{x}^T}\left( {{s_1}} \right)}\\ {{\textbf{x}^T}\left( {{s_2}} \right)}\\ {{\textbf{x}^T}\left( {{s_3}} \right)} \end{array}} \right) = \left( {\begin{array}{*{20}{c}} {{x_1}\left( {{s_1}} \right)}&{{x_2}\left( {{s_1}} \right)}\\ {{x_1}\left( {{s_2}} \right)}&{{x_2}\left( {{s_2}} \right)}\\ {{x_1}\left( {{s_3}} \right)}&{{x_2}\left( {{s_3}} \right)} \end{array}} \right)$$

On peut exprimer le vecteur des fonctions des valeurs des états de l'ensemble de l'environnement de la manière suivante:

$${V_\textbf{w}} = X \cdot \textbf{w}$$

Le vecteur des fonctions des valeurs des états est donc un vecteur dans $\mathbb{R}{^3}$. Pour une valeur optimale du vecteur poids $\textbf{w}=\textbf{w}^*$, on a les meilleures approximations possibles des valeurs des états :

Rappels sur l'aspect géométrique

L'erreur de Bellman $\overline {{\delta _\textbf{w}}} \left( s \right)$ permet de quantifier l'erreur entre la valeur d'un état obtenue à partir des fonctions d'approximations et les vraies valeurs. L'erreur de Bellman est également l'espérance de l'erreur TD :

On définit plusieurs mesures sur les vecteurs de ces fonctions des valeurs qui sont basées sur l'erreur de Bellman. En particulier, celle qui nous interesse ici est la valeur quadratique du projeté de l'erreur de Bellman:

Expression du projecteur orthogonal avec la norme usuelle

Pour trouver l'expression du projecteur orthogonal pondéré $\prod$, considérons la situation dans laquelle on cherche à projeter notre vrai vecteur des fonctions, ${V_\pi }$, vers le sous-espace vectoriel des fonctions approximées $V$ et considérons que la norme utilisée est la norme euclidienne usuelle ${\left\| \cdot \right\|^2}$.

Le théorème de décomposition orthogonal nous permet d'écrire le vecteur $V_\pi$ sous la forme d'une somme de deux vecteurs appartenant chacun dans des sous-espace vectoriels orthogonaux (décomposition orthogonale de $V_\pi$ par rapport au sous-espace vectoriel V) :

$${V_\pi } = {V_\textbf{w}} + V_\textbf{w}^ \bot$$

avec ${V_\textbf{w}} \in V$ et $V_\textbf{w}^ \bot \in {V^ \bot }$. Le sous-espace vectoriel ${V^ \bot }$ est le complément orthogonal du sous-espace vectoriel V tel que :

$${V^ \bot } = \left\{ {V |V \cdot W = 0,\forall W \in V} \right\}$$

Par exemple, dans l'exemple ci-dessous, le complément orthogonal de $V$ est une ligne perpendiculaire au plan $V$:

Par définition, on sait qu'il existe un vecteur $\textbf{w} \in \mathbb{R}{^2}$ tel que $X\textbf{w}=V_\textbf{w}$, donc on a la relation $(V_\pi-V_\textbf{w})=(V_\pi-X\textbf{w}) \in {V^ \bot }$.

On sait également que le vecteur des fonctions $V_\textbf{w}$ appartient au sous-espace vectoriel $V$, donc on peut écrire :

$$\left( {{V_\textbf{w}},{V_\pi } - {V_\textbf{w}}} \right) = 0$$

$$ \Rightarrow {\left( {{V_\textbf{w}}} \right)^T}\left( {{V_\pi } - {V_\textbf{w}}} \right) = 0$$

$$ \Rightarrow {\textbf{w}^T}{X^T}\left( {{V_\pi } - X\textbf{w}} \right) = 0$$

$$ \Rightarrow {X^T}{V_\pi } = {X^T}X\textbf{w}$$

$$ \Rightarrow \textbf{w} = {\left( {{X^T}X} \right)^{ - 1}}{X^T}{V_\pi }$$

On peut donc écrire finalement notre vecteur $V_\textbf{w}$ de la mnanière suivante :

$${V_\textbf{w}} = X\textbf{w} = X{\left( {{X^T}X} \right)^{ - 1}}{X^T}{V_\pi }$$

On en déduit donc l'expression du projecteur orthogonal avec la norme usuelle ${\left\| \cdot \right\|^2}$:

$$\prod = X{\left( {{X^T}X} \right)^{ - 1}}{X^T}$$

Expression du projecteur orthogonal pondéré

La norme utilisée pour mesurer les distances entre les vecteurs des fonctions des valeurs dans le sous-espace vectoriel $V$ est la suivante :

$$\left\| V \right\|_\mu ^2 = \sum\limits_s {\mu \left( s \right){V^2}}$$

Si on définit la matrice des distributions des états par:

$$D = \left( {\begin{array}{*{20}{c}} {\mu \left( {{s_1}} \right)}&0&0\\ 0&{\mu \left( {{s_2}} \right)}&0\\ 0&0&{\mu \left( {{s_3}} \right)} \end{array}} \right)$$

Alors on peut écrire la norme sous forme matricielle :

$$\left\| V \right\|_\mu ^2 = {V^T}DV$$

On peut donc maintenant écrire cette norme en fonction de la norme usuelle :

$$\left\| {{V_\pi } - {V_w}} \right\|_\mu ^2 = \left\| {{V_\pi } - X\textbf{w}} \right\|_\mu ^2 = \left( {{V_\pi } - X\textbf{w}} \right)^TD{\left( {{V_\pi } - X\textbf{w}} \right)}$$

$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \: \: \: = D\left( {{V_\pi } - X\textbf{w}} \right)^T{\left( {{V_\pi } - X\textbf{w}} \right)}$

$\quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \quad \: \: \: = {\left\| {{D^{1/2}}\left( {{V_\pi } - X\textbf{w}} \right)} \right\|^2}$

En conséquence, pour trouver l'expression du projecteur orthogonal pondéré, il suffit d'utiliser la relation suivante :

$$X \Leftrightarrow {D^{1/2}}X$$

On trouve donc:

$$\prod = {D^{1/2}}X{\left( {{{\left( {{D^{1/2}}X} \right)}^T}{D^{1/2}}X} \right)^{ - 1}}{\left( {{D^{1/2}}X} \right)^T}$$

$$\prod = X{\left( {{X^T}DX} \right)^{ - 1}}{X^T}D$$